#include <iostream>
#include <vector>
#include <set>

using namespace std;

class Solution {
private:
    struct TreeNode {
        int count = 0;
        int val;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode(int x) : val(x) {};
    };
    void insert_node(TreeNode*& node, int& val, int& count, vector<int>& nums, int& i) {
        if (node == nullptr) {
            node = new TreeNode(val);
            nums[i] = count;
            return;
        }
        if (val <= node->val) {
            node->count++;
            insert_node(node->left, val, count, nums, i);
        } else {
            count += (node->count + 1);
            insert_node(node->right, val, count, nums, i);
        }
    }
public:
    vector<int> countSmaller(vector<int>& nums) {
        TreeNode* node = nullptr;
        vector<int> ans(nums.size(), 0);
        for (int i = nums.size() - 1; i >= 0; i--) {
            int count = 0;
            insert_node(node, nums[i], count, ans, i);
        }
        return ans;
    }
};
int main() {
    vector<int> input = {5, 2, 6, 1};
    Solution solution;
    vector<int> output = solution.countSmaller(input);
    for (int item : output) {
        cout << item << endl;
    }
}